package cn.edu.njust.alg.leetcode;

/**
 * 创建时间：2015年6月15日 上午11:47:37 项目名称：AlgorithmExercise
 * 
 * @author Zhou Xiumin
 * @version 1.0
 * @since JDK 1.7.0_21 文件名称：Leetcode_0_t.java 类说明：
 */
public class Leetcode_91_Decode_Ways {

	public static int numDecodings(String s) {
		if (s == null || s.length() <= 0 || s.equals("0")) {
			return 0;
		}
		int[] dp = new int[s.length() + 1];
		dp[0] = 1;
		dp[1] = 1;
		char p, c;
		c = s.charAt(0);
		if (c == '0') {
			return 0;
		}
		p = s.charAt(0);
		for (int i = 1; i < s.length(); i++) {
			c = s.charAt(i);
			int pn = p - '0';
			int cn = c - '0';
			if ((pn == 0 || pn > 2) && cn == 0) {
				return 0;
			}
			if (cn == 0) {
				dp[i + 1] = dp[i - 1];
			} else if (pn == 1 || (pn == 2 && cn <= 6)) {
				dp[i + 1] = dp[i] + dp[i - 1];
			} else {
				dp[i + 1] = dp[i];
			}
			p = c;
		}
		return dp[s.length()];
	}

	public static void main(String[] args) {
		System.out.println(numDecodings("1231"));
		System.out.println(numDecodings("30"));
	}

}
